Search results for "Windy Rural Postman Problem"

showing 5 items of 5 documents

New Heuristic Algorithms for the Windy Rural Postman Problem

2005

[EN] In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented. (c) 2004 Elsevier Ltd. All rights reserved.

Arc routingMathematical optimizationGeneral Computer ScienceHeuristic (computer science)MetaheuristicsManagement Science and Operations ResearchRural postman problemSearch algorithmModeling and SimulationHeuristicsHeuristicsWindy rural postman problemMATEMATICA APLICADAArc routingAlgorithmMathematics
researchProduct

New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem

2011

[EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that t…

Postman problemsMathematical optimizationComputer Networks and CommunicationsFacetsWindy postman problemSet (abstract data type)Rural postman problemWindy rural postman problemsHardware and ArchitectureLarge set (Ramsey theory)Multi-vehiclesWindy rural postman problemMATEMATICA APLICADABranch and cutMetaheuristicAlgorithmsSoftwareMultivehicleInformation SystemsMathematicsNetworks
researchProduct

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

2013

[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.

Difficult problemService (systems architecture)Mathematical optimizationComputer Networks and CommunicationsBranch and priceColumn generationSet (abstract data type)Rural postman problemHardware and ArchitectureCutting planesGraph (abstract data type)Branch-and-priceColumn generationWindy rural postman problemMATEMATICA APLICADAAlgorithmSoftwareInformation SystemsMathematicsMultivehicle
researchProduct

Lower bounds and heuristics for the Windy Rural Postman Problem

2020

[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceHeuristic (computer science)Management Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringWindy Rural Postman ProblemModeling and SimulationCutting planesHeuristicsRouting (electronic design automation)HeuristicsMATEMATICA APLICADAAlgorithmArc routingCutting-plane methodMathematicsRouting
researchProduct

A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem

2016

[EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm…

Arc routingMathematical optimizationInformation Systems and ManagementGeneral Computer ScienceTotal costSnow removal0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringProfit (economics)Polyhedron0502 economics and businessWindy rural postman problemMathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cut algorithmModeling and SimulationMATEMATICA APLICADAArc routingAlgorithmBranch and cutPolyhedronProfits
researchProduct